import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        System.out.println("");
    }

    boolean[] vis;
    int ret;
    public int citys (ArrayList<ArrayList<Integer>> m) {
        // write code here
        vis = new boolean[m.size()];
        for (int i = 0;i < m.size();i++) {
            if (vis[i]) continue;
            dfs(i, m);
            ret++;
        }
        return ret;
    }
    public void dfs(int i , ArrayList<ArrayList<Integer>> m) {
        if (vis[i]) return;
        ArrayList<Integer> l = m.get(i);
        vis[i] = true;
        for (int j = 0;j < l.size();j++) {
            if (l.get(j) == 1) dfs(j , m);
        }
    }

    public int LIS1 (int[] a) {
        // write code here
        int n = a.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        for (int i = 0;i < n;i++) {
            dp[i] = 1;
            for (int j = 0;j < i;j++) {
                if (a[i] > a[j]) {
                    dp[i] = Math.max(dp[i] , dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public int LIS (int[] a) {
        // write code here
        int n = a.length;
        if (n == 0) return 0;
        int[] dp = new int[n + 1];
        int pos = 0;
        for (int x : a) {
            if (pos == 0 || x > dp[pos]) {
                dp[++pos] = x;
            }else {
                int l = 1, r = pos;
                while (l < r) {
                    int mid = (l + r) / 2;
                    if (dp[mid] >= x) r = mid;
                    else if (dp[mid] < x) l = mid + 1;
                }
                dp[l] = x;
            }
        }
        return pos;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        Map<Integer, ArrayList<Integer>> edges = new HashMap<>();
        for (int i = 0;i < prerequisites.length;i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];
            if (!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a);
            in[a]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0;i < numCourses;i++) {
            if (in[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int t = q.poll();
            for (int a : edges.getOrDefault(t, new ArrayList<>())) {
                in[a]--;
                if(in[a] == 0) q.add(a);
            }
        }
        for (int a : in) {
            if (a != 0) return false;
        }
        return true;
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        Map<Integer, ArrayList<Integer>> edges = new HashMap<>();
        int[] ret = new int[numCourses];
        for (int i = 0;i < prerequisites.length;i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];
            if (!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a);
            in[a]++;
        }
        Queue<Integer> q = new LinkedList<>();
        int pos = 0;
        for (int i = 0;i < numCourses;i++) {
            if (in[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int t = q.poll();
            ret[pos++] = t;
            for (int a : edges.getOrDefault(t, new ArrayList<>())) {
                in[a]--;
                if(in[a] == 0) q.add(a);
            }
        }
        for (int i = 0;i < numCourses;i++) {
            if (in[i] != 0) return new int[]{};
        }
        return ret;
    }

    Map<Character, Integer> in = new HashMap<>();
    Map<Character, Set<Character>> edges = new HashMap<>();
    boolean check;
    public String alienOrder(String[] words) {
        for (String s : words) {
            for (int i = 0;i < s.length();i++) {
                in.put(s.charAt(i), 0);
            }
        }
        for (int i = 0;i < words.length;i++) {
            for (int j = i + 1;j < words.length;j++) {
                add(words[i], words[j]);
                if (check) return "";
            }
        }
        Queue<Character> q = new LinkedList<>();
        StringBuffer sb = new StringBuffer();
        for (char ch : in.keySet()) {
            if (in.get(ch) == 0) q.add(ch);
        }
        while (!q.isEmpty()) {
            char ch = q.poll();
            sb.append(ch);
            for (char s : edges.getOrDefault(ch, new HashSet<>())) {
                in.put(s, in.get(s) - 1);
                if (in.get(s) == 0) q.add(s);
            }
        }
        for (char ch : in.keySet()) {
            if (in.get(ch) != 0) return "";
        }
        return sb.toString();
    }
    public void add (String s1, String s2) {
        int n = Math.min(s1.length(), s2.length());
        int i = 0;
        for (;i < n;i++) {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            if (c1 != c2) {
                if (!edges.containsKey(c1)) {
                    edges.put(c1, new HashSet<>());
                }
                if (!edges.get(c1).contains(c2)) {
                    edges.get(c1).add(c2);
                    in.put(c2, in.get(c2) + 1);
                }
                break;
            }
        }
        if (i == s2.length() && i < s1.length()) check = true;
    }

    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[] ret = new int[] {-1, -1};
        if (n == 0) return ret;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left]==target){
            ret[0]=left;
        }
        else{
            return ret;
        }
        right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        ret[1] = left;
        return ret;
    }

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0 , 1, -1};
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        boolean[][] vis = new boolean[n][m];
        int[][] ret = new int[n][m];
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (mat[i][j] == 0) {
                    q.add(new int[]{i, j});
                    ret[i][j] = 0;
                    vis[i][j] = true;
                }
            }
        }
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int i = t[0], j = t[1];
            for (int k = 0;k < 4;k++) {
                int x = dx[k] + i, y = dy[k] + j;
                if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]) {
                    ret[x][y] = ret[i][j] + 1;
                    q.add(new int[]{x, y});
                    vis[x][y] = true;
                }
            }
        }
        return ret;
    }

    public int numEnclaves(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[n][m];
        for (int i = 0;i < n;i++) {
            if (grid[i][0] == 1) {
                vis[i][0] = true;
                q.add(new int[] {i, 0});
            }
            if (grid[i][m - 1] == 1) {
                vis[i][m - 1] = true;
                q.add(new int[] {i, m - 1});
            }
        }
        for (int i = 1;i < m - 1;i++) {
            if (grid[0][i] == 1) {
                vis[0][i] = true;
                q.add(new int[]{0, i});
            }
            if (grid[n - 1][i] == 1) {
                vis[n - 1][i] = true;
                q.add(new int[] {n - 1, i});
            }
        }
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int i = t[0], j = t[1];
            for (int k = 0;k < 4;k++) {
                int x = dx[k] + i, y = dy[k] + j;
                if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1 && !vis[x][y]) {
                    q.add(new int[]{x, y});
                    vis[x][y] = true;
                }
            }
        }
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid[i][j] == 1 && !vis[i][j]) ret++;
            }
        }
        return ret;
    }

    public int[] topKFrequent(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < n;i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (pq.size() < k) pq.add(entry.getKey());
            else if (entry.getValue() > map.get(pq.peek())) {
                pq.poll();
                pq.add(entry.getKey());
            }

        }
        int[] ret = new int[k];
        for (int i = 0;i < k;i++) {
            ret[i] = pq.poll();
        }
        return ret;
    }

    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for (String str : strs) {
            char[] s = str.toCharArray();
            Arrays.sort(s);
            if (!hash.containsKey(new String(s))) {
                hash.put(new String(s), new ArrayList<>());
            }
            hash.get(new String(s)).add(str);
        }
        return new ArrayList<>(hash.values());
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for (String str : strs) {
            char[] s = str.toCharArray();
            int[] count = new int[26];
            for (int i = 0;i < s.length;i++) {
                count[s[i] - 'a']++;
            }
            StringBuffer sb = new StringBuffer();
            for (int i = 0;i < 26;i++) {
                if (count[i] != 0) {
                    sb.append((char) (i + 'a'));
                    sb.append(count[i]);
                }
            }
            String ss = sb.toString();
            if (!hash.containsKey(ss)) {
                hash.put(ss, new ArrayList<>());
            }
            hash.get(ss).add(str);
        }
        return new ArrayList<>(hash.values());
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        int n = maze.length, m = maze[0].length;
        boolean[][] vis = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;
        int step = 0;
        while (!q.isEmpty()) {
            step++;
            int sz = q.size();
            for (int i = 0;i < sz;i++) {
                int[] t = q.poll();
                int a = t[0], b = t[1];
                for (int j = 0;j < 4;j++) {
                    int x = a + dx[j], y = b + dy[j];
                    if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && maze[x][y] == '.') {
                        if (x == n - 1 || y == m - 1 || x == 0 || y == 0) return step;
                        q.add(new int[] {x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }

    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0;i < n;i++) dp[i][i] = true;

        int begin = 0, maxlen = 1;
        char[] arr = s.toCharArray();

        for (int i = 1;i < n;i++) {
            for (int j = 0;j < i;j++) {
                if (i - j < 2 && arr[i] == arr[j]) dp[j][i] = true;
                else if (arr[i] == arr[j]) dp[j][i] = dp[j + 1][i - 1];

                if (i - j + 1 > maxlen && dp[j][i]) {
                    maxlen = i - j + 1;
                    begin = j;
                }
            }
        }
        return s.substring(begin, begin + maxlen);
    }

    public int lastStoneWeight(int[] stones) {
        int n = stones.length;
        if (n == 1) return stones[0];
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 0;i < n;i++) pq.add(stones[i]);
        while (pq.size() > 1) {
            int a = pq.poll(), b = pq.poll();
            if (a != b) pq.add(a - b);
            if (pq.isEmpty()) return a - b;
        }
        if (!pq.isEmpty()) return pq.poll();
        return 0;
    }

    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> cnt = new HashSet<>();
        Set<String> vis = new HashSet<>();
        char[] keys = {'A', 'C', 'G', 'T'};
        for (String s : bank) {
            cnt.add(s);
        }
        if (startGene.equals(endGene)) return 0;
        if (!cnt.contains(endGene)) return -1;
        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step = 1;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0;i < sz;i++) {
                String s = q.poll();
                for (int j = 0;j < s.length();j++) {
                    for (int k = 0;k < 4;k++) {
                        if (s.charAt(j) != keys[k]) {
                            StringBuffer sb = new StringBuffer(s);
                            sb.setCharAt(j, keys[k]);
                            if (!vis.contains(sb.toString()) && cnt.contains(sb.toString())) {
                                if (sb.toString().equals(endGene)) return step;
                                vis.add(sb.toString());
                                q.add(sb.toString());
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }

    public int[][] highestPeak(int[][] isWater) {
        int n = isWater.length, m = isWater[0].length;
        int[][] ret = new int[n][m];
        for (int i = 0;i < n;i++) {
            Arrays.fill(ret[i], -1);
        }

        Queue<int[]> q = new LinkedList<>();
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (isWater[i][j] == 1) {
                    ret[i][j] = 0;
                    q.add(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int i = t[0], j = t[1];
            for (int k = 0;k < 4;k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < m && ret[x][y] == -1) {
                    ret[x][y] = ret[i][j] + 1;
                    q.add(new int[]{x, y});
                }
            }
        }
        return ret;
    }

    int n;
    public int maxDistance(int[][] grid) {
        n = grid.length;
        int ret = -1;

        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                if (grid[i][j] == 0) {
                    ret = Math.max(ret, findLand(i, j, grid));
                }
            }
        }
        return ret;
    }

    public int findLand (int i, int j,int[][] grid) {
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i, j, 0});
        vis[i][j] = true;
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for (int k = 0;k < 4;k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y]) {
                    q.add(new int[] {x,y, t[2] + 1});
                    vis[x][y] = true;
                    if (grid[x][y] == 1) return t[2] + 1;
                }
            }
        }
        return -1;
    }

    public void reorderList(ListNode head) {
        if (head == null) return;
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode l2 = slow.next;
        slow.next = null;
        l2 = reserve(l2);
        ListNode l1 = head;
        while (l1 != null && l2 != null) {
            ListNode next1 = l1.next, next2 = l2.next;
            l1.next = l2;
            l1 = next1;
            l2.next = l1;
            l2 = next2;
        }
    }

    public ListNode reserve(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] ss = new String[n];
        for (int i = 0;i < n;i++) {
            ss[i] = "" + nums[i];
        }
        Arrays.sort(ss, (a, b) -> (b + a).compareTo(a + b));
        if (ss[0].equals("0")) return "0";
        StringBuffer sb = new StringBuffer();
        for (String s : ss) {
            sb.append(s);
        }
        return sb.toString();
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return 0;
        Set<String> words = new HashSet<>();
        Set<String> vis = new HashSet<>();
        for (String s : wordList) {
            words.add(s);
        }
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        vis.add(beginWord);
        int ret = 1;
        while (!q.isEmpty()) {
            ret++;
            int sz = q.size();
            while (sz-- > 0) {
                String t = q.poll();
                for (int i = 0;i < t.length();i++) {
                    char[] arr = t.toCharArray();
                    for (char ch = 'a'; ch <= 'z';ch++) {
                        arr[i] = ch;
                        String next = new String(arr);
                        if (words.contains(next) && !vis.contains(next)) {
                            q.add(next);
                            vis.add(next);
                            if (next.equals(endWord)) return ret;
                        }
                    }
                }
            }
        }
        return 0;
    }

    int[][] g;
    int m;

    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size();
        n = forest.get(0).size();
        List<int[]> list = new ArrayList<>();
        g = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = forest.get(i).get(j);
                if (g[i][j] > 1)
                    list.add(new int[] { g[i][j], i, j });
            }
        }
        Collections.sort(list, (a, b) -> a[0] - b[0]);
        int x = 0, y = 0, ret = 0;
        for (int[] t : list) {
            int nx = t[1], ny = t[2];
            int ans = bfs(x, y, nx, ny);
            if (ans == -1)
                return -1;
            ret += ans;
            x = nx; y = ny;
        }
        return ret;
    }

    public int bfs(int x, int y, int nx, int ny) {
        if (x == nx && y == ny)
            return 0;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        q.add(new int[] { x, y });
        vis[x][y] = true;
        int ans = 1;
        while (!q.isEmpty()) {
            int sz = q.size();
            while (sz-- > 0) {
                int[] t = q.poll();
                int i = t[0], j = t[1];
                for (int k = 0; k < 4; k++) {
                    int a = i + dx[k], b = j + dy[k];
                    if (a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && g[a][b] != 0) {
                        q.add(new int[] { a, b });
                        vis[a][b] = true;
                        if (a == nx && b == ny) {
                            return ans;
                        }
                    }
                }
            }
            ans++;
        }
        return -1;
    }

    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        for (int i = 0;i < m;i++) {
            if (board[i][0] == 'O') {
                q.add(new int[]{i, 0});
                vis[i][0] = true;
            }
            if (board[i][n - 1] == 'O') {
                q.add(new int[]{i, n - 1});
                vis[i][n - 1] = true;
            }
        }
        for (int i = 0;i < n;i++) {
            if (board[0][i] == 'O') {
                q.add(new int[]{0, i});
                vis[0][i] = true;
            }
            if (board[m - 1][i] == 'O') {
                q.add(new int[]{m - 1, i});
                vis[m - 1][i] = true;
            }
        }
        while (!q.isEmpty()) {
            int[] t = q.poll();
            int i = t[0], j = t[1];
            for (int k = 0;k < 4;k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == 'O') {
                    q.add(new int[]{x, y});
                    vis[x][y] = true;
                }
            }
        }
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                if (board[i][j] == 'O' && !vis[i][j]) board[i][j] = 'X';
            }
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        List<String> ret = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> {
            if (map.get(a).equals(map.get(b))) return b.compareTo(a);
            return map.get(a) - map.get(b);
        });
        for (String word : map.keySet()) {
            if (pq.size() < k) {
                pq.add(word);
            } else  {
                if (map.get(word) > map.get(pq.peek())) {
                    pq.poll();
                    pq.add(word);
                }else if (map.get(word) == map.get(pq.peek()) && word.compareTo(pq.peek()) < 0) {
                    pq.poll();
                    pq.add(word);
                }
            }

        }
        while (!pq.isEmpty()) {
            ret.add(0, pq.poll());
        }
        return ret;

    }

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int num : stones) {
            sum += num;
        }
        int[] dp = new int[sum / 2 + 1];
        for (int i = 0;i < stones.length;i++) {
            for (int j = sum/2;j >= stones[i];j--) {
                dp[j] = Math.max(dp[j - stones[i]] + stones[i], dp[j]);
            }
        }
        return sum - 2 * dp[sum/2];
    }

    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1;i <= amount;i++) {
            for (int j = 0;j < n;j++) {
                if (i >= coins[j]) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (i >= j*j) {
                    dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
                }
            }
        }
        return dp[n];
    }

    public int wiggleMaxLength1(int[] nums) {
        int n = nums.length;
        if (n < 2) return n;
        int[] up = new int[n];
        int[] down = new int[n];
        up[0] = down[0] = 1;
        for (int i = 1;i < n;i++) {
            if (nums[i] > nums[i - 1]) {
                up[i] = Math.max(up[i - 1], down[i - 1] + 1);
                down[i] = down[i - 1];
            }else if (nums[i] < nums[i - 1]) {
                down[i] = Math.max(down[i - 1], up[i - 1] + 1);
                up[i] = up[i - 1];
            }else {
                down[i] = down[i - 1];
                up[i] = up[i - 1];
            }
        }
        return Math.max(down[n - 1], up[n - 1]);
    }

    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) return n;
        int ret = 0, left = 0, right = 0;
        for (int i = 0;i < n - 1;i++) {
            right = nums[i + 1] - nums[i];
            if (right == 0) continue;
            if (left * right <= 0) ret++;
            left = right;
        }
        return ret+1;
    }

    public int minNumberOfFrogs(String croakOfFrogs) {
        char[] arr = croakOfFrogs.toCharArray();
        String s = "croak";
        int n = s.length();
        int[] hash = new int[n];
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0;i < n;i++) {
            map.put(s.charAt(i), i);
        }
        for (char ch:arr) {
            if (map.get(ch) == 0) {
                if (hash[n - 1] > 0) {
                    hash[n - 1]--;
                }
                hash[0]++;
            }else {
                int i = map.get(ch);
                if (hash[i - 1] > 0) {
                    hash[i - 1]--;
                    hash[i]++;
                }else {
                    return -1;
                }
            }
        }
        for (int i = 0;i < n-1;i++) {
            if (hash[i] != 0) return -1;
        }
        return hash[n-1];
    }

    public String longestPalindrome2(String s) {
        int n = s.length();
        if (n < 2) return s;
        boolean[][] dp = new boolean[n][n];
        for (int i = 0;i < n;i++) dp[i][i] = true;

        int begin = 0, maxlen = 1;
        char[] arr = s.toCharArray();

        for (int i = 1;i < n;i++) {
            for (int j = 0;j < i;j++) {
                if (i - j < 2 && arr[i] == arr[j]) dp[j][i] = true;
                else if (arr[i] == arr[j]) dp[j][i] = dp[j + 1][i - 1];

                if (i - j + 1 > maxlen && dp[j][i]) {
                    maxlen = i - j + 1;
                    begin = j;
                }
            }
        }
        return s.substring(begin, begin + maxlen);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int i=0;
        List<List<Integer>> list=new ArrayList<>();
        for(i=0;i<nums.length-2;++i){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            if(nums[i]+nums[i+1]+nums[i+2]>0){
                break;
            }
            if (nums[i]+nums[nums.length-2] + nums[nums.length-1]<0){
                continue;
            }
            int end=nums.length-1;
            int start=i+1;
            while(start<end){
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0){
                    list.add(List.of(nums[i],nums[start],nums[end]));
                    while(start<end&&nums[start]==nums[start+1]){
                        start++;
                    }
                    start++;
                    while(start<end&&nums[end]==nums[end-1]){
                        end--;
                    }
                    end--;
                }
                else if(sum>0){
                    end--;
                }
                else{
                    start++;
                }
            }
        }
        return list;
    }

    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int ret = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (rightMax < leftMax) {
                ret += rightMax - height[right--];
            }else {
                ret += leftMax - height[left++];
            }
        }
        return ret;
    }

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            Deque<Integer> list = new LinkedList<>();
            for (int i = 0;i < size;i++) {
                TreeNode node = queue.poll();
                if (flag) {
                    list.offerLast(node.val);
                }
                else {
                    list.offerFirst(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(new ArrayList<>(list));
            flag = !flag;
        }
        return result;
    }

    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        boolean cur = false;
        if (root.val > pre) cur = true;
        pre = root.val;
        boolean right = isValidBST(root.right);
        return cur&&left&&right;
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode next = cur.left;
                TreeNode prev = next;
                while (prev.right != null) {
                    prev = prev.right;
                }
                prev.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;
        }
    }

    public int maxProduct(int[] nums) {
        int n=nums.length;
        int[] f=new int[n+1];
        int[] g=new int[n+1];
        f[0]=g[0]=1;
        int ret=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            f[i]=Math.max(nums[i-1],Math.max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
            g[i]=Math.min(nums[i-1],Math.min(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
            ret=Math.max(ret,f[i]);
        }
        return ret;
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<>();
        for (int i = 0;i < intervals.length;i++) {
            int l = intervals[i][0], r = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < l) {
                merged.add(new int[]{l, r});
            }else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], r);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    public int myAtoi(String str) {
        int n = str.length();
        int i = 0;
        // 记录正负号
        int sign = 1;
        // 用 long 避免 int 溢出
        long res = 0;
        // 跳过前导空格
        while (i < n && str.charAt(i) == ' ') {
            i++;
        }
        if (i == n) {
            return 0;
        }

        // 记录符号位
        if (str.charAt(i) == '-') {
            sign = -1;
            i++;
        } else if (str.charAt(i) == '+') {
            i++;
        }
        if (i == n) {
            return 0;
        }

        // 统计数字位
        while (i < n && '0' <= str.charAt(i) && str.charAt(i) <= '9') {
            res = res * 10 + str.charAt(i) - '0';
            if (res > Integer.MAX_VALUE) {
                break;
            }
            i++;
        }
        // 如果溢出，强转成 int 就会和真实值不同
        if ((int) res != res) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        return (int) res * sign;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int[] pSum = new int[26];
        int[] sSum = new int[26];
        for (char ch : p.toCharArray()) {
            pSum[ch - 'a']++;
        }
        for (int right = 0;right < s.length();right++) {
            sSum[s.charAt(right) - 'a']++;
            int left = right - p.length() + 1;
            if (left < 0) continue;
            if (Arrays.equals(pSum, sSum)) {
                ret.add(left);
            }
            sSum[s.charAt(left) - 'a']--;
        }
        return ret;
    }

    public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length,n=dungeon[0].length;
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<=n;i++){
            dp[m][i]=Integer.MAX_VALUE;
        }
        for(int i=0;i<=m;i++){
            dp[i][n]=Integer.MAX_VALUE;
        }
        dp[m-1][n]=1;
        dp[m][n-1]=1;
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }

    boolean[][] row, col;
    boolean[][][] grid;
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(board);
    }
    public boolean dfs (char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int num = 1;num <= 9;num++) {
                        if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                            board[i][j] = (char) (num + '0');
                            if (dfs(board)) return true;
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    public List<Integer> findSubstring(String ss, String[] tt) {
        List<Integer> ret=new ArrayList<>();
        Map<String,Integer> hash1=new HashMap<>();
        int n=tt.length,m=tt[0].length();
        for(String t:tt){
            hash1.put(t,hash1.getOrDefault(t,0)+1);
        }
        for(int i=0;i<m;i++){
            Map<String,Integer> hash2=new HashMap<>();
            for(int left=i,right=i,count=0;right+m<=ss.length();right+=m){
                String in=ss.substring(right,right+m);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in)<=hash1.getOrDefault(in,0)) count++;
                if(right-left+1>m*n){
                    String out=ss.substring(left,left+m);
                    if(hash2.get(out)<=hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out)-1);
                    left+=m;
                }
                if(count==n) ret.add(left);
            }
        }
        return ret;
    }


    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> multi_stack = new LinkedList<>();
        LinkedList<String> res_stack = new LinkedList<>();
        for (Character c:s.toCharArray()) {
            if (c == '[') {
                multi_stack.addLast(multi);
                res_stack.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                int k = multi_stack.removeLast();
                for (int i = 0; i < k;i++) tmp.append(res);
                res = new StringBuilder(res_stack.removeLast() + tmp);
            }else if(c >= '0' && c <= '9'){
                multi = multi * 10 + Integer.parseInt(c + "");
            }else {
                res.append(c);
            }
        }
        return res.toString();
    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int[] pSum = new int[26];
        int[] sSum = new int[26];
        for (char ch : p.toCharArray()) {
            pSum[ch - 'a']++;
        }
        for (int right = 0;right < s.length();right++) {
            sSum[s.charAt(right) - 'a']++;
            int left = right - p.length() + 1;
            if (left < 0) continue;
            if (Arrays.equals(pSum, sSum)) {
                ret.add(left);
            }
            sSum[s.charAt(left) - 'a']--;
        }
        return ret;
    }

    public int maxArea(int[] height) {
        int left=0,right=height.length-1;
        int max=0;
        while(left<right){
            if(height[right]<height[left]){
                max=Math.max(max,(right-left)*height[right]);
                right--;
            }
            else{
                max=Math.max(max,(right-left)*height[left]);
                left++;
            }
        }
        return max;
    }

}

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
  class Read {
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
  }